package com.yangli.leecode.mashib.interview;

import java.util.Stack;

/**
 * @Description
 * @Author liyang
 * @Date 2023/3/6 15:48
 */
public class ThirtyFive {
    public static void main(String[] args){

        System.out.println(ThirtyFive.removeDuplicateLetters("cbacdcbc"));

    }


    public static String removeDuplicateLetters(String s) {
        char [] chars = s.toCharArray();
        Stack<Character> stack = new Stack<Character>();
        int[] count = new int[256];//
        for (int i = 0; i < s.length(); i++) {
            count[s.charAt(i)]++;
        }
        boolean[] inStack = new boolean[256];

        for (int i = 0; i <chars.length ; i++) {
            //每次都会把字符次数统计
            count[chars[i]]--;
            //如果字典顺序不正确，取出，但是要注意如果剩的是最后一个字符了不能取出
            while (!stack.empty()&&stack.peek()>chars[i]){
                if(count[stack.peek()]==0){
                    break;
                }
                inStack[stack.pop()] = false;
            }

            //表示这个字符是不是重复入过栈
            if (inStack[chars[i]]) continue;

            stack.push(chars[i]);
            inStack[chars[i]] = true;


        }
        StringBuilder sb = new StringBuilder();
        while (!stack.empty()) {
            sb.append(stack.pop());
        }

        return sb.reverse().toString();

    }




}
